

public class Main1 {
    public static void main(String[] args) {
        // 初始化一个链表
        ListNode head = new ListNode(2);
        ListNode node1 = new ListNode(3);
        ListNode node2 = new ListNode(7);
        ListNode node3 = new ListNode(10);
        ListNode node4 = new ListNode(1);
        ListNode node5 = new ListNode(5);
        ListNode node6 = new ListNode(14);
        //ListNode head2 = new ListNode(19);

        head.next = node1;
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node6;
        //head2.next = node3;
        head.print();
        System.out.println("**************************");

        //ListNode[] listArray = {head,node4};
        //findLastKthNode(head,4).print();
        //deleteNode(head,4).print();
        //reverseList2(head).print();
        //findCommonNode(head,head2).print();
        //mergeTwoLists(head,node4).print();
        //mergeKLists1(listArray).print();
        //swapEachTwoNodes2(head).print();
        //reverseKGroup(head,4).print();
        //reverseBetween(head,2,4).print();

        System.out.println(hasCycle(head));
    }

    // 返回单链表倒数第k个节点
    public static ListNode findLastKthNode(ListNode head,int k){

        if(head==null || k <= 0) return null;

        ListNode first = head;  // 快指针
        ListNode slow = head;   // 慢指针

        for (int i = 0; i < k; i++) {
            if(first == null) return null;  // 防止K过大
            first = first.next;
        }

        while(first != null){
            first = first.next;
            slow = slow.next;
        }
        return slow;
    }


    // 删除链表中值为指定值的第一个节点
    public static ListNode deleteNode(ListNode head,int value){
        if(head == null) return head;
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode pre = dummy;
        ListNode cur = dummy.next;
        while(cur != null){
            if(cur.value == value){
                pre.next = cur.next;
                break;   // 删除此行表示删除所有值为value的节点
            }
            pre = cur;
            cur = cur.next;
        }
        return dummy.next;
    }


    // 单链表反转 ： 递归
    public static ListNode reverseList1(ListNode head){
        if(head == null || head.next == null) return head;
        ListNode p = reverseList1(head.next);
        head.next.next = head;
        head.next = null;
        return p;
    }

    // 反转链表 ： 迭代
    public static ListNode reverseList2(ListNode head){
        if(head == null || head.next == null) return head;
        ListNode cur = head;
        ListNode pre = null;
        ListNode next;
        while (cur!=null){
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

    // 求两个链表的第一个公共节点
    public static ListNode findCommonNode(ListNode head1,ListNode head2){
        if(head1 == null || head2 == null) return null;
        ListNode p1 = head1;
        ListNode p2 = head2;
        while (p1 != p2){  // 齐头并进

            if(p1 == null){
                p1 = head2;
            }else{
                p1 = p1.next;
            }

            if(p2 == null){
                p2 = head1;
            }else{
                p2 = p2.next;
            }
        }
        return p1;
    }


    // 合并两个有序链表
    public static ListNode mergeTwoLists(ListNode p1,ListNode p2){
        ListNode dummy = new ListNode(-1);  // 假节点
        ListNode flag = dummy;
        while (p1!=null && p2!=null){
            if(p1.value <= p2.value){
                flag.next = p1;
                p1 = p1.next;
            }else{
                flag.next = p2;
                p2 = p2.next;
            }
            flag = flag.next;
        }

        if(p1 != null) flag.next = p1;
        if(p2 != null) flag.next = p2;
        return dummy.next;

    }


    // 合并K个链表
    // 方法1：迭代合并，利用7.1的方法
    public static ListNode mergeKLists1(ListNode[] lists) {
        if(lists.length == 0) return null;
        if(lists.length == 1) return lists[0];
        ListNode dummy = mergeTwoLists(lists[0],lists[1]);
        for(int i=2; i<lists.length; i++){
            dummy = mergeTwoLists(dummy,lists[i]);
        }
        return dummy;
    }


    // 方法2：分而治之：效率更高 类似于归并排序，利用7.1的方法
    public static ListNode mergeKLists2(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;
        return merge(lists, 0, lists.length - 1);
    }
    public static ListNode merge(ListNode[] lists, int left, int right) {
        if (left == right) return lists[left]; // 递归停止条件
        int mid = left + (right - left) / 2;
        ListNode l1 = merge(lists, left, mid);
        ListNode l2 = merge(lists, mid + 1, right);
        return mergeTwoLists(l1, l2);
    }


    // 两两交换链表中的节点
    // 递归
    public static ListNode swapEachTwoNodes1(ListNode head){
        if(head == null || head.next == null) return head;
        ListNode next = head.next;
        ListNode p = swapEachTwoNodes1(next.next);
        head.next = p;
        next.next = head;
        return next;
     }


     // 迭代
    public static ListNode swapEachTwoNodes2(ListNode head){
        if(head == null || head.next == null) return head;

        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode pre = dummy;

        while (head!=null && head.next!=null){
            ListNode f = head;
            ListNode s = head.next;

            pre.next = s;
            f.next = s.next;
            s.next = f;

            head = f.next;
            pre = f;
        }
        return dummy.next;
    }


    // k个一组反转链表
    public static ListNode reverseKGroup(ListNode head, int k) {
        if(head == null || head.next == null || k <= 1) return head;
        ListNode dummy = new ListNode(-1);
        ListNode pre = dummy;
        dummy.next = head;
        ListNode start = head;
        ListNode end = head;
        ListNode newSubListHead = head;

        while (newSubListHead!=null){
            for (int i = 1; i < k && end != null; i++) {
                end = end.next;
            }
            if(end == null) break;  // 表示这一段节点数不够k个

            newSubListHead = end.next;
            end.next = null;  //这里断开以获得小的链表
            end = start;
            start = reverseList2(start);
            end.next = newSubListHead;
            pre.next = start;

            // 重新指定pre start end
            pre = end;
            start = newSubListHead;
            end = newSubListHead;
        }
        return dummy.next;
    }

    // 反转链表 II
    // 反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
    public static ListNode reverseBetween(ListNode head, int m, int n) {
        if(head == null || head.next == null) return head;
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode pre = dummy;
        ListNode newHead;
        for (int i = 1; i < m ; i++) {
            pre = pre.next;
        }
        newHead = pre.next;

        for (int i = m; i < n; ++i) {
            ListNode next = newHead.next;
            newHead.next = next.next;
            next.next = pre.next;
            pre.next = next;
        }
        return dummy.next;
    }


    private static void reverse(ListNode prev, ListNode last) {

        ListNode pre = last.next, cur = prev.next, nxt;
        while (cur != last) {
            nxt = cur.next;
            cur.next = pre;
            pre = cur;
            cur = nxt;
        }
        cur.next = pre;
        prev.next = last;

    }


    // 环形链表I
    public static boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }
        ListNode fast = head.next;
        ListNode slow = head;
        while (slow != fast){
            if (fast == null || fast.next == null) {
                return false;
            }
            fast = fast.next.next;
            slow = slow.next;
        }
        return true;
    }

    // 环形链表II 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
    public static ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) {
            return null;
        }

        ListNode fast = head.next;
        ListNode slow = head;
        while (slow != fast){
            if (fast == null || fast.next == null) {
                return null;
            }
            fast = fast.next.next;
            slow = slow.next;
        }

        ListNode third = head;
        while (third != slow){
            slow = slow.next;
            third = third.next;
        }
        return third;
    }




}
